package com.lmz.project.redis.arithmetic.heapShed;


import static com.lmz.project.redis.arithmetic.heapShed.LinkTest.ListNode;

/**
 * 合并两个有序链表
 * 计算两个链表的和
 * 划分链表
 */
public class LinkTest1 {

    public static void main(String[] args) {
        ListNode list1 = new ListNode(2);
        ListNode list1Next1 = new ListNode(4);
        ListNode list1Next2 = new ListNode(3);
        list1Next1.next = list1Next2;
        list1.next = list1Next1;

        ListNode list2 = new ListNode(5);
        ListNode list2Next1 = new ListNode(6);
        ListNode list2Next2 = new ListNode(4);
        list2Next1.next = list2Next2;
        list2.next = list2Next1;
//        ListNode listNode = mergeTwoLists(list1, list2);
//        ListNode listNode1 = sumTwoLists(list1, list2);
//        System.out.println(listNode);
//        ListNode listNode1 = separateListNode(listNode, 4);
//        System.out.println(listNode1);
//        System.out.println(listNode);

    }

    //合并两个有序链表
    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null || list2 == null) {
            return list1 == null ? list2 : list1;
        }
        ListNode head = list1.val <= list2.val ? list1 : list2;
        ListNode curr1 = head.next;
        ListNode curr2 = head == list1 ? list2 : list1;
        ListNode pre = head;
        while (curr1 != null && curr2 != null) {
            if (curr1.val <= curr2.val) {
                pre.next = curr1;
                curr1 = curr1.next;
            } else {
                pre.next = curr2;
                curr2 = curr2.next;
            }
            pre = pre.next;
        }
        pre.next = curr1 == null ? curr2 : curr1;

        return head;
    }

    //测试地址：https://leetcode.cn/problems/merge-two-sorted-lists/
    public ListNode mergeTwoLists1(ListNode list1, ListNode list2) {
        if (list1 == null || list2 == null) {
            return list1 == null ? list2 : list1;
        }
        ListNode head = list1.val <= list2.val ? list1 : list2; //记录较小的头节点
        ListNode curr1 = head.next; //记录较小头节点的下一个节点
        ListNode curr2 = head == list1 ? list2 : list1; //记录较大的头节点
        ListNode ans = head;
        while (curr1 != null && curr2 != null) {
            if (curr1.val <= curr2.val) {
                head.next = curr1;
                curr1 = curr1.next;
            }else {
                head.next = curr2;
                curr2 = curr2.next;
            }
            head = head.next;
        }
        //将余下的节点全部穿到一起
        head.next = curr1 == null ? curr2 : curr1;
        return ans;
    }

    /**
     * 对两个链表求和
     *
     * @param list1
     * @param list2
     * @return 测试地址 https://leetcode.cn/problems/sum-lists-lcci/submissions/575107639/
     */

    public static ListNode sumTwoLists(ListNode list1, ListNode list2) {
        ListNode ans = null;
        ListNode cur = null;
        int carry = 0; // 记录进位
        for (ListNode h1 = list1, h2 = list2;
             h1 != null || h2 != null;
             h1 = h1 == null ? null : h1.next,
                     h2 = h2 == null ? null : h2.next
        ) {
            int sum = (h1 == null ? 0 : h1.val) + (h2 == null ? 0 : h2.val) + carry;
            int remainder = sum % 10;
            carry = sum / 10;
            if (ans == null) {
                ans = new ListNode(remainder);
                cur = ans;
            } else {
                cur.next = new ListNode(remainder);
                cur = cur.next;
            }
        }

        if (carry == 1) {
            cur.next = new ListNode(1);
        }

        return ans;
    }


    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) {
            return l1 == null ? l2 : l1;
        }
        int curry = 0; //进位
        ListNode ans = null;
        ListNode pre = null;
        for (ListNode h1 = l1, h2 = l2; h1 != null || h2 != null; h1 = h1 == null ? h1 : h1.next, h2 = h2 == null ? h2 : h2.next) {
            int sum = (h1 == null ? 0 : h1.val) + (h2 == null ? 0 : h2.val) + curry;
            curry = sum / 10;
            int count = sum % 10;
            if (ans == null) {
                ans = new ListNode(count);
                pre = ans;
            } else {
                pre.next = new ListNode(count);
                pre = pre.next;
            }
        }
        if (curry == 1) {
            pre.next = new ListNode(1);
        }
        return ans;
    }


    /**
     * 划分链表
     *
     * @param head 当前链表
     * @param x    目标值
     * @return 划分后的链表
     */
    public static ListNode separateListNode(ListNode head, int x) {
        ListNode maxHead = null, maxTail = null;
        ListNode minHead = null, minTail = null;
        ListNode next = null;
        while (head != null) {
//            next = head.next;
//            head.next = null;
            if (head.val < x) {
                if (minHead == null) {
                    minHead = head;
                } else {
                    minTail.next = head;
                }
                minTail = head;
            } else {
                if (maxHead == null) {
                    maxHead = head;
                } else {
                    maxTail.next = head;
                }
                maxTail = head;
            }
            head.next = null;
            next = head.next;
            head = next;
        }
        if (minHead == null) {
            return maxHead;
        }
        if (maxHead != null) {
            minTail.next = maxHead;
        }
        return minHead;
    }

}
